package 数据结构.图;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * Created by 编程只服JAVA on 2016.12.01.
 */

public class GraphByAdjacencyList {
    // 图的顶点集合
    private Set<Vertex> vertexSet = new HashSet<GraphByAdjacencyList.Vertex>();
    // 相邻的结点,利用链表保存相邻结点
    Map<Vertex, List<Vertex>> adjaencys = new HashMap<GraphByAdjacencyList.Vertex, List<Vertex>>();

    public GraphByAdjacencyList() {
    }

    public GraphByAdjacencyList(Set<Vertex> vertexs,Map<Vertex, List<Vertex>> adjaencys) {
        this.vertexSet = vertexs;
        this.adjaencys = adjaencys;
        for (Vertex vertex : vertexSet) {
            vertex.isVisable = false;
        }
    }

    public Set<Vertex> getVertexSet() {
        return vertexSet;
    }

    public Map<Vertex, List<Vertex>> getAdjaencys() {
        return adjaencys;
    }

    /**
     * 深度优先搜索(默认图是联通的)
     */
    public void depthFirstSearch(GraphByAdjacencyList graph , Vertex vertex){
        Map<Vertex, List<Vertex>> map = graph.getAdjaencys();//得到所有边的集合
        List<Vertex> list = map.get(vertex);//得到要遍历的结点的邻接点的集合

        System.out.println(vertex.name);//打印边的左（开始）结点
        vertex.isVisable = true;//将已经打印过的置为true
        if (list != null && list.size() > 0) {
            for (Vertex vertex2 : list) {
                if (vertex2.isVisable == false) {
                    depthFirstSearch(graph, vertex2);//递归的遍历每一个结点
                }
            }
        }
    }

    public void setIsviable(){
        for (Vertex vertex : vertexSet) {
            vertex.isVisable = false;
        }
    }

    /**
     * 广度优先搜索  (图的遍历都要设置好isVisable(),否则都会陷入到无尽的循环中)
     * @param graph
     * @param vertex 指定进行广度优先搜索的结点
     */
    public void broadFirstSearch(GraphByAdjacencyList graph,Vertex vertex){
        graph.setIsviable();
        Map<Vertex, List<Vertex>> map = graph.getAdjaencys();
        Queue<Vertex> queue = new LinkedList<GraphByAdjacencyList.Vertex>();//创建一个队列
        queue.add(vertex);

        while(!queue.isEmpty()){
            Vertex poll = queue.poll();
            System.out.println(poll.name);
            poll.isVisable = true;
            List<Vertex> pollList = map.get(poll);

            if(pollList != null && !pollList.isEmpty()){
                for (Vertex vertex2 : pollList) {
                    if (vertex2.isVisable == false) {
                        queue.add(vertex2);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        // 构造顶点集合
        Vertex vertex0 = new Vertex(0);
        vertex0.weight = 121;
        Vertex vertex1 = new Vertex(1);
        Vertex vertex2 = new Vertex(2);
        Vertex vertex3 = new Vertex(3);
        Vertex vertex4 = new Vertex(4);

        // 构造顶点集合
        Set<Vertex> vertices = new HashSet<GraphByAdjacencyList.Vertex>();
        vertices.add(vertex0);
        vertices.add(vertex1);
        vertices.add(vertex2);
        vertices.add(vertex3);
        vertices.add(vertex4);

        Map<Vertex, List<Vertex>> map0 = new HashMap<GraphByAdjacencyList.Vertex, List<Vertex>>();
        LinkedList<Vertex> linkedList0 = new LinkedList<GraphByAdjacencyList.Vertex>();
        linkedList0.add(vertex1);
        linkedList0.add(vertex2);

        LinkedList<Vertex> linkedList2 = new LinkedList<GraphByAdjacencyList.Vertex>();
        linkedList2.add(vertex3);

        LinkedList<Vertex> linkedList3 = new LinkedList<GraphByAdjacencyList.Vertex>();
        linkedList3.add(vertex0);

        map0.put(vertex0, linkedList0);
        map0.put(vertex2, linkedList2);
        map0.put(vertex3, linkedList3);

        GraphByAdjacencyList graphByAdjacencyList = new GraphByAdjacencyList(vertices, map0);
        for (Vertex vertex : graphByAdjacencyList.getVertexSet()) {
            List<Vertex> adjencyList = graphByAdjacencyList.getAdjaencys().get(vertex);
            if (adjencyList!=null) {
                for (Vertex vertex5 : adjencyList) {
                    System.out.println("顶点："+vertex.name+"的边有"+vertex.name+"--->"+vertex5.name);
                }
            }
        }

        graphByAdjacencyList.depthFirstSearch(graphByAdjacencyList, vertex0);
        System.out.println("广度优先遍历");
        graphByAdjacencyList.broadFirstSearch(graphByAdjacencyList, vertex0);
    }

    static class Vertex {
        public int name;
        public int weight;//权重
        public boolean isVisable;

        public Vertex(int data) {
            this.name = data;
        }
    }
}
